#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define M_RATE 0.0
#define MAXTRY 10
typedef struct Meb{
    double value;
    int    lable;
}Meb;

Meb* kMeans(Meb *S, int num, Meb *kMeb, int k);
double distXY(double x, double y);
int Kstop_cond(Meb *S, int num, Meb *KMeb, int k);
int ReCalcK(Meb *S, int num, Meb *KMeb, int k);
double CalcSSE(Meb *S, int num, Meb *kMeb, int k);

int TkMeans()
{
    int i, iTryCnt;
    Meb *s, *kMeb, *minkMeb;
    double dSSE = 0.0, dminSSE = -1;

    kMeb = (Meb *)malloc(2 * sizeof(Meb));
    minkMeb = (Meb *)malloc(2 * sizeof(Meb));
    s = (Meb *)malloc(10 * sizeof(Meb));
    memset(s, 0, 10*sizeof(Meb));
    for(i=0;i<=10;i++)
    {
       s[i].value = i;
       s[i].lable = -1;
    }

    srand((unsigned)time( NULL ));
    for(iTryCnt=0;iTryCnt<10; iTryCnt++)
    {
        kMeans(s, 10, kMeb, 2);
        dSSE = CalcSSE(s, 10, kMeb, 2);
        printf("[%f][%f]SSE=[%f]\n", kMeb[0].value, kMeb[1].value, dSSE); 
        if(dminSSE < 0 || dSSE < dminSSE)
        {
           dminSSE = dSSE;
           memcpy(minkMeb, kMeb, 2 * sizeof(Meb));
        }
    }
    printf("[%f][%f]minSSE=[%f]\n", minkMeb[0].value, minkMeb[1].value, dminSSE); 
}

Meb* kMeans(Meb *S, int num, Meb *kMeb, int k)
{
    int Kh[k], i, Cnt[k], MCnt = 0;

    memset(Kh, 0, sizeof(Kh));
    memset(kMeb, 0, k*sizeof(Meb));
//    srand((unsigned)time( NULL ));
    for(i=0; i<k; i++)
    {
       Kh[i] = rand() % num;
       memcpy(kMeb + i, S + Kh[i], sizeof(Meb));
       printf("Kh=[%d]\n", Kh[i]);
    }

    ReCalcK(S, num, kMeb, k);
    for(i=0; i<k; i++)
    {
       printf("KMeb[%d]=[%f]\n", i, kMeb[i].value);
    }

    return kMeb;
}
int Kstop_cond(Meb *S, int num, Meb *KMeb, int k)
{
    int i, j, MCnt = 0;
    double minDist, dist = 0.0;
    Meb *OriMeb;
   
    OriMeb = (Meb *)malloc(num*sizeof(Meb)); 
    memcpy(OriMeb, S, num*sizeof(Meb));
    for(i=0;i<num;i++)
    {
       minDist = distXY(S[i].value, KMeb[0].value) + 1;
       for(j=0;j<k;j++)
       {
          dist = distXY(S[i].value, KMeb[j].value);
          if(dist < minDist)
          {
             minDist = dist;
             S[i].lable = j;
          }
       }
    }

    for(i=0;i<num;i++)
    {
       if(S[i].lable != OriMeb[i].lable)
       {
          MCnt ++;
       }
    }

    if (num*M_RATE >= MCnt)
       return 1;
    else 
       return 0;    
}

int ReCalcK(Meb *S, int num, Meb *KMeb, int k)
{
    int i, j, Cnt[k];
    double Sum[k];

    memset(Sum, 0, sizeof(Sum));
    memset(Cnt, 0, sizeof(Cnt));
    for(i=0; i<k; i++)
    {
       printf("KMeb[%d]=[%f]\n", i, KMeb[i].value);
    }
    if(Kstop_cond(S, num, KMeb, k) == 1)
    {
       return 0;
    } else
    {
       for(i=0;i<k;i++)
       {
          for(j=0;j<num;j++)
          {
             if(S[j].lable == i)
             {
                Cnt[i] ++;
                Sum[i] = Sum[i] + S[j].value;
             }
          }
          KMeb[i].value = Sum[i]/Cnt[i];
       }
       ReCalcK(S, num, KMeb, k);
    }
    return 0;
}

double distXY(double x, double y)
{
    return sqrt((x-y)*(x-y));
}

double CalcSSE(Meb *S, int num, Meb *kMeb, int k)
{
    int i, j;
    double dSSE = 0.0;
    double dDist = 0.0;
    for(j=0;j<num;j++)
    {
       dDist = distXY(S[j].value, kMeb[S[j].lable].value);
       dSSE =dSSE + dDist * dDist;
    }
    return dSSE;
}
